#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m = triangle.size();

        vector<vector<int>> f(m + 1, vector<int>(m + 1, INT_MAX));

        f[0][0] = triangle[0][0];
        for (int i = 1; i < m; i++) {
            f[i][0] = f[i - 1][0] + triangle[i][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j <= i; j++) {
                f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
            }
        }
        int ans = INT_MAX;
        for (int i = 0; i < m; i++) {
            ans = min(ans, f[m - 1][i]);
        }
        return ans;
    }
};